#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


template<typename T>
bool cmp(T a, T b)
{
    return a > b;
}


template<typename T>
void BlumSort(vector<T>& nums)
{
    for(int i=1; i<nums.size(); i++)
    {
        bool flag = false;
        for(int j=0; j<nums.size()-i; j++)
        {
            if(cmp(nums[j], nums[j+1]))
            {
                T tmp = nums[j+1];
                nums[j+1] = nums[j];
                nums[j] = tmp;
                flag = true;
            }
        }
        if(!flag) break;
    }
}




template<typename T>
void InsertSort(vector<T>& nums)
{
    for(int i=1; i<nums.size(); i++)
    {
        T tmp = nums[i];
        int j=i;
        for(; j>0 && cmp(nums[j-1], tmp); j--)
        {    
            nums[j] = nums[j-1];
        }
        nums[j] = tmp;
    }
    
}


template<typename T>
void SelectSort(vector<T>& nums)
{
    for(int i=0; i<nums.size()-1; i++)
    {
        int argtmp = i;
        for(int j=i+1; j<nums.size(); j++)
        {
            if(cmp(nums[argtmp], nums[j]))
            {
                argtmp = j;
            }
        }
        T tmp = nums[argtmp];
        nums[argtmp] = nums[i];
        nums[i] = tmp;
    }
}




int main(){

    vector<int> nums = {2,1,4,4,4,7,-1,39,27,14,99};

    for(int i : nums) printf("%d ", i);
    printf("\n");


    // InsertSort(nums);
    // BlumSort(nums);
    SelectSort(nums);

    for(int i : nums) printf("%d ", i);
    printf("\n");

    return 0;
}

